package 我的Java学习_算法基础.day_04;

public class _066_编程返回子数组最大累加和 {
    /**
     * 给定一个数组arr，返回子数组的最大累加和
     *
     * 子数组：数组中连续的数据
     *
     * 例：arr={1,-2,3,5,-2,6,-1},所有的子数组中{3,5,-2,6}可以累加出最大的和12，所以返回12
     */
    public static void main(String[] args) {
        int[] a ={1,-2,3,5,-2,6,-1};
//        int[] a ={1,-2,-4,-7};
        findByForce(a);
        findByDP(a);
    }

    /**
     * 暴力解法(O(N^2))
     * @param array
     */
    private static void findByForce(int[] array){
        int maxSum = array[0];
        for(int i =0;i< array.length;i++){
            int sum = array[i];
            int maxOfI = sum;
            for(int j =i+1;j<array.length;j++){
                sum+=array[j];
                if(sum>maxOfI){
                    maxOfI=sum;
                }
            }
            if(maxOfI>maxSum){
                maxSum=maxOfI;
            }
        }
        System.out.println(maxSum);
    }

    /**
     * 递推法(O(N))
     * 记录出现的连续累加最大值
     * 如果前面累计和出现负数，则舍弃
     * 从当前数与后面进行累加
     * @param a
     */
    public static int findByDP(int[] a){
        int sumI =a[0];
        int max = sumI;
        int left=0,right=0,step=0;
        for(int i = 1;i<a.length;i++){
            if(sumI>0){
                sumI+=a[i];
                //left=i;  不行，新的连加不一定大于旧的，但right一定是对的，故引入step
                step++;
            }else{
                sumI = a[i];
                step=0;
            }
            if(sumI>max){
                max=sumI;   //刷新最大值
                right=i;
                left = right-step;
            }
        }
        System.out.println(max+":from"+left+"to"+right);
        return max;
    }
}
